//package 题目集.动态规划;
//
//import org.junit.Test;
//
//import java.util.Arrays;
//
///**
// * 给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
// * 返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
// * https://leetcode.cn/problems/max-submatrix-lcci/description/
// */
//public class ch03_最大子矩阵 {
//    /**
//     * dp[i][j]：以i,j为右下角的矩阵的最大和
//     *      可选操作：
//     *          要之前的矩阵
//     *          不要之前的矩阵
//     *      dp[i][j]=max (matrix[i][j],matrix[i][j]+max(dp[i-1][j],dp[i][j-1]))
//     *      在遍历过程中记录最大值
//     */
//    public int[] getMaxMatrix(int[][] matrix) {
//        init(matrix);
//        int[] res = new int[]{0, 0, 0, 0};
//        int max = Integer.MIN_VALUE;
//        for (int i = 1; i <= n; i++) {
//            for (int j = 1; j <= m; j++) {
//                int choseUp = sum(dp[i - 1][j][0], dp[i - 1][j][1], i, j);
//                int choseLeft = sum(dp[i][j - 1][0], dp[i][j - 1][1], i, j);
//                int[] chose;
//                int choseSum=0;
//                if (choseLeft >= choseUp) {
//                    chose = dp[i][j - 1];
//                    choseSum = choseLeft;
//                } else {
//                    chose = dp[i - 1][j];
//                    choseSum = choseUp;
//                }
//                if (matrix[i - 1][j - 1] >= choseSum) {
//                    dp[i][j][0] = i;
//                    dp[i][j][1] = j;
//                } else {
//                    dp[i][j][0] = chose[0];
//                    dp[i][j][1] = chose[1];
//                }
//                int cur = sum(dp[i][j][0], dp[i][j][1], i, j);
//                if (cur > max) {
//                    max = cur;
//                    res[0] = dp[i][j][0];
//                    res[1] = dp[i][j][1];
//                    res[2] = i;
//                    res[3] = j;
//                }
//            }
//        }
//        for (int i = 0; i < res.length; i++) {
//            res[i]--;
//        }
//        return res;
//    }
//
//    public int sum(int lx, int ly, int rx, int ry) {
//        return sum[rx][ry] - sum[lx-1][ry] - sum[rx][ly-1] + sum[lx-1][ly-1];
//    }
//
//    int[][][] dp;   //多一维记录左上角,0左上角x，1左上角y
//    int[][] sum;
//    int n, m;
//
//    public void init(int[][] matrix) {
//        n = matrix.length;
//        m = matrix[0].length;
//        dp = new int[matrix.length + 1][matrix[0].length + 1][2];
//        sum = new int[matrix.length + 1][matrix[0].length + 1];
//        for (int i = 0; i < dp.length; i++) {
//            dp[i][0][0] = 1;
//            dp[i][0][1] = 1;
//        }
//        for (int i = 0; i < dp[0].length; i++) {
//            dp[0][i][0] = 1;
//            dp[0][i][1] = 1;
//        }
//        for (int i = 1; i <= n; i++) {
//            for (int j = 1; j <= m; j++) {
//                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
//            }
//        }
//    }
//
//    @Test
//    public void test() {
////        int[][] matrix = {
////                {9, -8, 1, 3, -2},
////                {-3, 7, 6, -2, 4},
////                {6, -4, -4, 8, -7}
////        };
//        //[[-1, -2, -9, 6], [8, -9, -3, -6], [2, 9, -7, -6]]
////        int[][] matrix = {
////                {-1, -2, -9, 6},
////                {8, -9, -3, -6},
////                {2, 9, -7, -6}
////        };
//        int[][] matrix = {
//                {-1, -1},
//                {8, -9},
//                {2, 9}
//        };
//        int[] maxMatrix = getMaxMatrix(matrix);
//        for (int i : maxMatrix) {
//            System.out.println(i);
//        }
//    }
//}
